#!/usr/bin/python
#
# exp.py - Classes to represent underlying data structures for the grammar
#	 below, for the mini-compiler.
#
# Kurt Schmidt
# 8/07
#
# DESCRIPTION:
#		Just a translation of the C++ implementation by Jeremy Johnson (see
#		programext.cpp)
#
# EDITOR: cols=80, tabstop=2
#
# NOTES
#	environment:
#		a dict
#
#		Procedure calls get their own environment, can not modify enclosing env
#
#	Grammar:
#		program: stmt_list 
#		stmt_list:  stmt ';' stmt_list 
#		    |   stmt  
#		stmt:  assign_stmt 
#		    |  if_stmt 
#		    |  while_stmt 
#		assign_stmt: IDENT ASSIGNOP expr
#		define_stmt: DEFINE IDENT PROC '(' param_list ')' stmt_list END
#		if_stmt: IF expr THEN stmt_list ELSE stmt_list FI
#		while_stmt: WHILE expr DO stmt_list OD
#		expr: expr '+' term   
#		    | expr '-' term   
#		    | term            
#		term: term '*' factor   
#		    | factor            
#		factor:     '(' expr ')'  
#		    |       NUMBER 
#		    |       IDENT 
#

import sys

####  CONSTANTS   ################

	# the variable name used to store a proc's return value
returnSymbol = 'return'

tabstop = '  ' # 2 spaces

######   CLASSES   ##################

class TableEntry:
	'''For storing values in the tables'''
	def __init__(self, string, value):
		self.string = string
		self.value = value


class fTableEntry:
	def __init__(self, name, ar, ilist, numParams, numLocals, numTemps):
		self.name = name
		self.ar = []
		for i in range(0, len(ar)):
			self.ar.append(ar[i])
		self.ilist = []
		for j in range(0, len(ilist)):
			self.ilist.append(ilist[j])
		self.paramCount = numParams
		self.localCount = numLocals
		self.tempCount = numTemps
		#the extra 3 are for rtnvalue, prevfp, rtnaddress
		self.size = self.paramCount + self.localCount + self.tempCount + 2
class Instruction :
	'''Class for the RAM instructions'''

	def __init__ (self, func, operand, lineNum, varType):
		#func will be a string the function we call i.e. JMP or LD
		self.func = func
		#The argument if any
		self.operand = operand
		#Its line number
		self.lineNum = lineNum
		#type of variable used
		self.varType = varType
		#idea- field to set linked operand
		self.linkedoperand = ""
		self.linkedfunc = ""
class RAMInfo:
	'''Hold all info related to creating RAM programs'''
	def __init__(self):
		#instrList is the list or Instructions
		self.instrList = []
		#the counters are used for when we need to retrieve the next const, label, or temp
		self.constCount = 1
		self.labelCount = 1
		self.tempCount = 1
		self.lineCount = 1
		#the tables hold their respective variable
		self.constTable = []
		self.constValueTable = [] 
		self.localTable = []
		self.tempTable = []
		self.labelTable = []
		#stuff for A5
		self.fParamCount = 1
		self.fTempCount = 1
		self.fLocalCount = 1
		self.fParamTable = []
		self.fTempTable = []
		self.fLocalTable = []
		#differentiates between defining a proc and normal
		self.currentFunction = "main"
		self.fInstrList = []
		self.funcTable = []
	
	def getNextTemp(self):
		result = "T" + str(self.tempCount)
		self.tempCount = self.tempCount +1
		return result

	def getNextLabel(self):
		result = "L" + str(self.labelCount)
		self.labelCount = self.labelCount + 1
		return result
	
	def getNextConst(self, value):
		isFound = 0
		for i in range(0,len(self.constValueTable)):
			if(self.constValueTable[i].value == value):
				isFound = 1
				return self.constValueTable[i].string
		if isFound == 0:
			result = "C" + str(self.constCount)
			self.constValueTable.append(TableEntry(result, value))
			self.constCount = self.constCount + 1
			return result

	def getNextParam(self):
		result = "P" + str(self.fParamCount)
		self.fParamCount = self.fParamCount + 1
		return result

	def getNextFTemp(self):
		result = "FT" + str(self.fTempCount)
		self.fTempCount = self.fTempCount + 1
		return result

	def getNextFLocal(self):
		result = "FL" + str(self.fLocalCount)
		self.fLocalCount  = self.fLocalCount + 1
		return result

	def addInstr(self, func, operand, type):
		instr = Instruction(func, operand, self.lineCount, type)
		self.instrList.append(instr)
		self.lineCount = self.lineCount + 1

	def addfInstr(self, func, operand, type):
		#line numbers will be fixed when put into main instr list
		instr = Instruction(func, operand, 0, type)
		self.fInstrList.append(instr)

	def addLabel(self, lbl):
		instr = Instruction("LBL", lbl, self.lineCount, "LABEL")
		print "LineCount = "+ str(self.lineCount)
		if(self.currentFunction == "main"):
			self.instrList.append(instr)
		else:
			self.fInstrList.append(instr)
	
	#maybe include nme of func as param
	def dumpAR(self):
		print "Param Table"
		for i in range(0, len(self.fParamTable)):
			print self.fParamTable[i].string+ "---->" + str(self.fParamTable[i].value)


		print "Local Table"
		for j in range(0, len(self.fLocalTable)):
			print self.fLocalTable[j].string+ "---->" + str(self.fLocalTable[j].value)

		print "Temp Table"
		for k in range(0, len(self.fTempTable)):
			print self.fTempTable[k].string+ "---->" + str(self.fTempTable[k].value)

	#this will add in a function temp/local into the appropriate temple
	def addToAR(self, name, type):
		
		if(type == "TEMP"):
			isFound = 0
			for i in range(0, len(self.fTempTable)):
				if(self.fTempTable[i].string == name):
					isFound = 1
			if(isFound == 0):
				self.fTempTable.append(TableEntry(name, 0))

		if(type == "LOCAL"):
			isFound = 0
			for i in range(0, len(self.fLocalTable)):
				if(self.fLocalTable[i].string == name):
					isFound = 1
			if(isFound == 0):
				self.fLocalTable.append(TableEntry(name, 0))

	def buildAR(self, name):
		ar = []
		returnPresent = 0
		for i in range(0, len(self.fParamTable)):
			ar.append(TableEntry(self.fParamTable[i].string, self.fParamTable[i].value))
		for j in range(0, len(self.fLocalTable)):
			if(self.fLocalTable[j].string == "return"):
				returnPresent = 1
			else:
				ar.append(TableEntry(self.fLocalTable[j].string, self.fLocalTable[j].value))
		for k in range(0, len(self.fTempTable)):
			ar.append(TableEntry(self.fTempTable[k].string, self.fTempTable[k].value))
		if( returnPresent == 1):
			ar.append(TableEntry("return",0))
		
		self.funcTable.append(fTableEntry(name, ar, self.fInstrList,len(self.fParamTable),len(self.fLocalTable),len(self.fTempTable)))
		#for testing
#		for l in range(0, len(ar)):
#			print ar[l].string+" "+str(ar[l].value)

	#if it works, could modify to take a name param to search for specific functions
	def fTableDump(self):
		print "RAM Function Table"
		
		for i in range(0, len(self.funcTable)):
			print "RAM function Name: "+ self.funcTable[i].name
			print "AR for: "+self.funcTable[i].name
			for j in range(0, len(self.funcTable[i].ar)):
				print self.funcTable[i].ar[j].string
			print"Instruction List for: " +self.funcTable[i].name
			for k in range(0, len(self.funcTable[i].ilist)):
				print self.funcTable[i].ilist[k].func+" "+self.funcTable[i].ilist[k].operand


	def instrDump(self, tail=""):
		programFile = open('program' + tail + '.ral','w')
		for p in range(0, len(self.instrList)):
			if(self.instrList[p].func != "NULL"): 
				programFile.write(self.instrList[p].func +" "+str(self.instrList[p].operand) +"\n")
				#print self.instrList[p].func +" "+str(self.instrList[p].operand)
		programFile.close()

	def memoryDump(self):
		memoryFile = open('memory.ral','w')
		memoryFile.write('1 0\n')#FP
		memoryFile.write('2 ' + str(4 + len(self.constTable)+len(self.localTable)+len(self.tempTable))  + '\n')#SP
		memoryFile.write('3 0\n')#FPB
		memoryFile.write('4 0\n')#SCRATCH
		print "CONST " + str(len(self.constTable)) + " LOCAL " + str(len(self.localTable)) + " TEMP " + str(len(self.tempTable)) + "\n"
		for i in range(0, len(self.constTable)):
			value = -1
			for l in range(len(self.constValueTable)):
				if self.constValueTable[l].string == self.constTable[i].string:
					value = self.constValueTable[l].value
					break
			memoryFile.write(str(self.constTable[i].value) + " "+ str(value) +"\n")
			#print self.constTable[i].string + "----->"+ str(self.constTable[i].value)
		for j in range(0, len(self.localTable)):
			memoryFile.write(str(self.localTable[j].value) + " 0 ;local value of " + self.localTable[j].string + "\n")
			#print self.localTable[j].string + "----->"+ str(self.localTable[j].value)
		for k in range(0, len(self.tempTable)):
			memoryFile.write(str(self.tempTable[k].value) + " 0 ;Temporary value " + self.tempTable[k].string + "\n")
			#print self.tempTable[k].string + "----->"+ str(self.tempTable[k].value)
		#for l in range(0, len(self.labelTable)):
			#print self.labelTable[l].string+ "----->"+ str(self.labelTable[l].value)
		memoryFile.close()

	def link(self):
		memCounter = 5;

		for p in range(0, len(self.instrList)):
			if self.instrList[p].varType == "FP":
				self.instrList[p].operand = 1 #HARDCODED TO BE THE FP
			if self.instrList[p].varType == "SP":
				self.instrList[p].operand = 2 #HARDCODED VALUE OF THE SP
			if self.instrList[p].varType == "FPB":
				self.instrList[p].operand = 3 #HARDCODED VALUE OF THE FPB
			if self.instrList[p].varType == "SCRATCH":
				self.instrList[p].operand = 4 #HARDCODED VALUE OF THE SCRATCH
			
			if(self.instrList[p].varType == "CONST"):
				isFound = 0
				for i in range(0, len(self.constTable)):
					if(self.constTable[i].string == self.instrList[p].operand):
						self.instrList[p].operand = self.constTable[i].value
						isFound = 1
				if isFound == 0:
					print "CONST FOUND, MEMCOUNTER IS " + str(memCounter)
					self.constTable.append(TableEntry(self.instrList[p].operand, memCounter))
					self.instrList[p].operand = memCounter
					if self.instrList[p].func == "LD":
						self.instrList[p].func = "LDA"
					if self.instrList[p].func == "ST":
						self.instrList[p].func = "STA"
					memCounter = memCounter + 1
		for p in range(0, len(self.instrList)):
			if(self.instrList[p].varType == "LOCAL"):
				isFound = 0
				for i in range( 0, len(self.localTable)):
					if(self.localTable[i].string == self.instrList[p].operand):
						self.instrList[p].operand = self.localTable[i].value
						isFound = 1
				if isFound == 0:
					self.localTable.append(TableEntry(self.instrList[p].operand, memCounter))	
					self.instrList[p].operand = memCounter
					if self.instrList[p].func == "LD":
						self.instrList[p].func = "LDA"
					if self.instrList[p].func == "ST":
						self.instrList[p].func = "STA"
					memCounter = memCounter + 1
		for p in range(0, len(self.instrList)):
			if(self.instrList[p].varType == "TEMP"):
				isFound = 0
				for i in range(0, len(self.tempTable)):
					if(self.tempTable[i].string == self.instrList[p].operand):
						self.instrList[p].operand = self.tempTable[i].value
						isFound = 1
				if isFound == 0:
					self.tempTable.append(TableEntry(self.instrList[p].operand, memCounter))
					print self.instrList[p].operand
					self.instrList[p].operand = memCounter
					if(self.instrList[p].func == "LD"):
						self.instrList[p].func = "LDA"
					if(self.instrList[p].func == "ST"):
						self.instrList[p].func = "STA"
					memCounter = memCounter  + 1
					print "Size of temp Table -> " + str(len(self.tempTable))
		for p in range(0, len(self.instrList)):
			if(self.instrList[p].func == "LBL" and self.instrList[p].varType == "LABEL"):
				isFound = 0
				for i in range(0, len(self.labelTable)):
					if(self.labelTable[i].string == self.instrList[p].operand):
						self.instrList[p].operand = self.labelTable[i].value
						isFound = 1
				if isFound == 0:
					self.labelTable.append(TableEntry(self.instrList[p].operand, self.instrList[p].lineNum))
					self.instrList[p].operand = self.instrList[p].lineNum
					memCounter = memCounter + 1
				self.instrList[p].func = "NULL"

		for p in range(0, len(self.instrList)):
			if(self.instrList[p].func != "NULL" and self.instrList[p].varType == "LABEL"):
				for i in range(0, len(self.labelTable)):
					if(self.labelTable[i].string == self.instrList[p].operand):
						self.instrList[p].operand = self.labelTable[i].value 
class Expr :
	'''Virtual base class for expressions in the language'''

	def __init__( self ) :
		raise NotImplementedError(
			'Expr: pure virtual base class.  Do not instantiate' )

	def eval( self, nt, ft ) :
		'''Given an environment and a function table, evaluates the expression,
		returns the value of the expression (an int in this grammar)'''

		raise NotImplementedError(
			'Expr.eval: virtual method.  Must be overridden.' )

	def translate(self, nt, ri):

		raise NotImplementedError('Expr.translate: virtual method. Must be overrridden.'+str(self))

	def display( self, nt, ft, depth=0 ) :
		'For debugging.'
		raise NotImplementedError(
			'Expr.display: virtual method.  Must be overridden.' )

class Number( Expr ) :
	'''Just integers'''

	def __init__( self, v=0 ) :
		self.value = v
	
	def eval( self, nt, ft ) :
		return self.value

	def translate(self, nt, ri) :
		if(ri.currentFunction == "main"):
			con = ri.getNextConst(self.value)
			temp1 = ri.getNextTemp()
			ri.addInstr("LD", con, "CONST")
			ri.addInstr("ST", temp1, "TEMP")
		else:
			con = ri.getNextConst(self.value)
			temp1 = ri.getNextFTemp()
			ri.addfInstr("LD", con, "CONST")
			ri.addfInstr("ST", temp1, "TEMP")
			ri.addToAR(temp1, "TEMP")
		return temp1

	def display( self, nt, ft, depth=0 ) :
		print "%s%i" % (tabstop*depth, self.value)

class Ident( Expr ) :
	'''Stores the symbol'''

	def __init__( self, name ) :
		self.name = name
	
	def eval( self, nt, ft ) :
		return nt[ self.name ]

	def translate(self, nt, ri):
		if(ri.currentFunction == "main"):
			temp1 = ri.getNextTemp()
			ri.addInstr("LD", self.name, "LOCAL")
			ri.addInstr("ST", temp1, "TEMP")
		else:
			temp1 = ri.getNextFTemp()
			ri.addfInstr("LD", self.name, "LOCAL")
			ri.addfInstr("ST", temp1, "TEMP")
			ri.addToAR(temp1, "TEMP")
		return temp1

	def display( self, nt, ft, depth=0 ) :
		print "%s%s" % (tabstop*depth, self.name)


class Times( Expr ) :
	'''expression for binary multiplication'''

	def __init__( self, lhs, rhs ) :
		'''lhs, rhs are Expr's, the operands'''

		# test type here?
		# if type( lhs ) == type( Expr ) :
		self.lhs = lhs
		self.rhs = rhs
	
	def eval( self, nt, ft ) :
		return self.lhs.eval( nt, ft ) * self.rhs.eval( nt, ft )

	def translate(self, nt, ri):

		temp1 = self.lhs.translate(nt, ri)
		temp2 = self.rhs.translate(nt, ri)
		if(ri.currentFunction == "main"):
			temp3 = ri.getNextTemp()
			ri.addInstr("LD", temp1, "TEMP")
			ri.addInstr("MUL", temp2, "TEMP")
			ri.addInstr("ST", temp3, "TEMP")
		else:
			temp3 = ri.getNextFTemp()
			ri.addfInstr("LD", temp1, "TEMP")
			ri.addfInstr("MUL", temp2, "TEMP")
			ri.addfInstr("ST", temp3, "TEMP")
			ri.addToAR(temp1, "TEMP")
			ri.addToAR(temp2, "TEMP")
			ri.addToAR(temp3, "TEMP")
		return temp3

	def display( self, nt, ft, depth=0 ) :
		print "%sMULT" % (tabstop*depth)
		self.lhs.display( nt, ft, depth+1 )
		self.rhs.display( nt, ft, depth+1 )
		#print "%s= %i" % (tabstop*depth, self.eval( nt, ft ))


class Plus( Expr ) :
	'''expression for binary addition'''

	def __init__( self, lhs, rhs ) :
		self.lhs = lhs
		self.rhs = rhs
	
	def eval( self, nt, ft ) :
		return self.lhs.eval( nt, ft ) + self.rhs.eval( nt, ft )

	def translate(self, nt, ri):

		temp1 = self.lhs.translate(nt, ri)
		temp2 = self.rhs.translate(nt, ri)
		if(ri.currentFunction == "main"):
			temp3 = ri.getNextTemp()
			ri.addInstr("LD", temp1, "TEMP")
			ri.addInstr("ADD", temp2, "TEMP")
			ri.addInstr("ST", temp3, "TEMP")
		else:
			temp3 = ri.getNextFTemp()
			ri.addfInstr("LD", temp1, "TEMP")
			ri.addfInstr("ADD", temp2, "TEMP")
			ri.addfInstr("ST", temp3, "TEMP")
			ri.addToAR(temp1, "TEMP")
			ri.addToAR(temp2, "TEMP")
			ri.addToAR(temp3, "TEMP")
		return temp3	

	def display( self, nt, ft, depth=0 ) :
		print "%sADD" % (tabstop*depth)
		self.lhs.display( nt, ft, depth+1 )
		self.rhs.display( nt, ft, depth+1 )
		#print "%s= %i" % (tabstop*depth, self.eval( nt, ft ))


class Minus( Expr ) :
	'''expression for binary subtraction'''

	def __init__( self, lhs, rhs ) :
		self.lhs = lhs
		self.rhs = rhs
	
	def eval( self, nt, ft ) :
		return self.lhs.eval( nt, ft ) - self.rhs.eval( nt, ft )

	def translate(self, nt, ri):

		temp1 = self.lhs.translate(nt, ri)
		temp2 = self.rhs.translate(nt, ri)
		if(ri.currentFunction == "main"):
			temp3 = ri.getNextTemp()
			ri.addInstr("LD", temp1, "TEMP")
			ri.addInstr("SUB", temp2, "TEMP")
			ri.addInstr("ST", temp3, "TEMP")
		else:
			temp3 = ri.getNextFTemp()
			ri.addfInstr("LD", temp1, "TEMP")
			ri.addfInstr("SUB", temp2, "TEMP")
			ri.addfInstr("ST", temp3, "TEMP")
			ri.addToAR(temp1, "TEMP")
			ri.addToAR(temp2, "TEMP")
			ri.addToAR(temp3, "TEMP")
		return temp3

	def display( self, nt, ft, depth=0 ) :
		print "%sSUB" % (tabstop*depth)
		self.lhs.display( nt, ft, depth+1 )
		self.rhs.display( nt, ft, depth+1 )
		#print "%s= %i" % (tabstop*depth, self.eval( nt, ft ))


class FunCall( Expr ) :
	'''stores a function call:
	- its name, and arguments'''

	def __init__( self, name, argList ) :
		self.name = name
		self.argList = argList

	def eval( self, nt, ft ) :
		return ft[ self.name ].apply( nt, ft, self.argList )

	def translate(self, nt, ri):
		funcIndex = -1
		#STORE THE CURRENT FP
		temp1 = ri.getNextTemp()
		ri.addInstr("LDA","FP","FP")
		ri.addInstr("STA",temp1, "TEMP")
		#REPLACE THE FP WITH THE SP
		one = ri.getNextConst(1)
		ri.addInstr("LDA","SP","SP")
		ri.addInstr("ADD",one,"CONST")
		ri.addInstr("STA","FP","FP")
		functionDef = ""
		for funRecord in ri.funcTable:
			if funRecord.name == self.name:
				functionDef = funRecord
				
#		print "HERE"+str(functionDef.size)
		#update SP
		size = ri.getNextConst(functionDef.size)
		ri.addInstr("LDA", "FP", "FP")
		ri.addInstr("ADD", size, "CONST")
		ri.addInstr("STA", "SP", "SP")

		#store previous FP
		ri.addInstr("LDA", "SP", "SP")
		ri.addInstr("SUB", one, "CONST")
		ri.addInstr("STA", "FPB", "FPB")
		ri.addInstr("LDA", temp1, "TEMP")
		ri.addInstr("STI", "FPB", "FPB")
		ri.addInstr("STA","FPB","FPB")

		if len(self.argList) != funRecord.paramCount:
			print "In a call to " + self.name + " there was an incorrect number of parameters. The function defition expected " + str(funRecord.paramCount) + "and there were " + str(len(self.argList)) + " given."
			exit(1)
		for paramIndex in range(funRecord.paramCount):
			#Generate the code to evaluate the value of the parameter
			self.argList[paramIndex].translate(nt, ri)
			#Store it at the location pointed to by the FPB
			ri.addInstr("STI","FPB","FPB")
			#Then update the FPB, and restore it
			ri.addInstr("LDA","FPB","FPB")
			ri.addInstr("ADD",one,"CONST")
			ri.addInstr("STA","FPB","FPB")
		#NOW,JUST INITIALIZE ALL THE LOCALS AND TEMPS TO 0
		#ADD ONE FOR THE RETURN VALUE
		zero = ri.getNextConst(0)
		for dummyIndex in range(funRecord.localCount + funRecord.tempCount + 1):
			ri.addInstr("LDA",zero,"CONST")
			ri.addInstr("STI","FPB","FPB")
			ri.addInstr("LDA","FPB","FPB")
			ri.addInstr("ADD",one,"CONST")
			ri.addInstr("ST","FPB","FPB")
		
		#grab return value
		ri.addInstr("LDA", "SP", "SP")
		two = ri.getNextConst(2)
		ri.addInstr("SUB", two, "CONST")
		ri.addInstr("STA", "FPB", "FPB")
		ri.addInstr("LDI", "FPB", "FPB")
		temp3 = ri.getNextTemp()
		ri.addInstr("LDA", temp3, "TEMP")
		
		#get previous fp
		ri.addInstr("LDA", "SP", "SP")
		ri.addInstr("SUB", one, "CONST")
		ri.addInstr("STA", "FPB", "FPB")
		ri.addInstr("LDI", "FPB", "FPB")
		ri.addInstr("STA", "SCRATCH", "SCRATCH")
		

		#Restore sp
		ri.addInstr("LDA", "FP", "FP")
		ri.addInstr("STA", "SP", "SP")

		#Restore fp
		ri.addInstr("LDA", "SCRATCH", "SCRATCH")
		ri.addInstr("STA", "FP", "FP")
		return temp3
		#LOAD IN THE PREV FP, and store it
#		ri.addInstr("LD",temp1,"TEMP")
#		ri.addInstr("STI","FPB","FPB")
#		ri.addInstr("LD","FPB","FPB")
#		ri.addInstr("ADD",one,"CONST")
#		ri.addInstr("ST","FPB","FPB")
		#NOW, JUST LOAD IN THE RETURN ADDRESS AND CALL IT A DAY
#		returnAddr = ri.getNextLabel()
#		ri.addInstr("LD",returnAddr,"LABEL")
#		ri.addInstr("STI","FPB","FPB")
	def display( self, nt, ft, depth=0 ) :
		print "%sFunction Call: %s, args:" % (tabstop*depth, self.name)
		for e in self.argList :
			e.display( nt, ft, depth+1 )



#-------------------------------------------------------

class Stmt :
	'''Virtual base class for statements in the language'''

	def __init__( self ) :
		raise NotImplementedError(
			'Stmt: pure virtual base class.  Do not instantiate' )

	def eval( self, nt, ft ) :
		'''Given an environment and a function table, evaluates the expression,
		returns the value of the expression (an int in this grammar)'''

		raise NotImplementedError(
			'Stmt.eval: virtual method.  Must be overridden.' )

	def translate(self, nt, ri):
		
		raise NotImplementedError('Stmt.translate: virtual method. Must be overridden')	

	def display( self, nt, ft, depth=0 ) :
		'For debugging.'
		raise NotImplementedError(
			'Stmt.display: virtual method.  Must be overridden.' )


class AssignStmt( Stmt ) :
	'''adds/modifies symbol in the current context'''

	def __init__( self, name, rhs ) :
		'''stores the symbol for the l-val, and the expressions which is the
		rhs'''
		self.name = name
		self.rhs = rhs
	
	def eval( self, nt, ft ) :
		nt[ self.name ] = self.rhs.eval( nt, ft )

	
	def translate(self, nt, ri):
		temp1 = self.rhs.translate( nt, ri)
		if(ri.currentFunction == "main"):
 			ri.addInstr("LD", temp1, "TEMP")
			ri.addInstr("ST", self.name, "LOCAL")
		else:
			if self.name != returnSymbol: 
				ri.addfInstr("LD", temp1, "TEMP")
				ri.addToAR(temp1, "TEMP")
				ri.addfInstr("ST", self.name, "LOCAL")
				ri.addToAR(self.name, "LOCAL")
			else:
				#STORE THE RETURN VALUE
				temp2 = ri.getNextFTemp()
				one = ri.getNextConst(1)
				ri.addfInstr("LD","SP","SP")
				#Rather than create two constants, just create one, and run it twice
				ri.addfInstr("SUB",one,"CONST")
				ri.addfInstr("SUB",one,"CONST")
				#Temp2 points at the return address
				ri.addfInstr("ST",temp2,"TEMP")
				ri.addfInstr("LD", temp1, "TEMP")
				ri.addfInstr("STI",temp2,"TEMP")
				#JUMP TO RA, THE RA IS IN SP
				ri.addfInstr("JMI","SP","SP")

	def display( self, nt, ft, depth=0 ) :
		print "%sAssign: %s :=" % (tabstop*depth, self.name)
		self.rhs.display( nt, ft, depth+1 )

class DefineStmt( Stmt ) :
	'''Binds a proc object to a name'''

	def __init__( self, name, proc ) :
		self.name = name
		self.proc = proc

	def eval( self, nt, ft ) :
		ft[ self.name ] = self.proc

	def translate(self, nt, ri):
		ri.currentFunction =self. name
		ri.addLabel(self.name)
		self.proc.translate(nt,ri)
		ri.buildAR(self.name)
		ri.fTableDump()
	def display( self, nt, ft, depth=0 ) :
		print "%sDEFINE %s :" % (tabstop*depth, self.name)
		self.proc.display( nt, ft, depth+1 )



class IfStmt( Stmt ) :

	def __init__( self, cond, tBody, fBody ) :
		'''expects:
		cond - expression (integer)
		tBody - StmtList
		fBody - StmtList'''
		
		self.cond = cond
		self.tBody = tBody
		self.fBody = fBody

	def eval( self, nt, ft ) :
		if self.cond.eval( nt, ft ) > 0 :
			self.tBody.eval( nt, ft )
		else :
			self.fBody.eval( nt, ft )

	def translate(self, nt, ri):
		temp1 = self.cond.translate(nt,ri)
		label1 = ri.getNextLabel()
		label2 = ri.getNextLabel()
		if(currentFunction == "main"):
			ri.addInstr("LD", temp1, "TEMP")
			ri.addInstr("JMN", label1, "LABEL")
			ri.addInstr("JNZ", label1, "LABEL")
			self.tBody.translate(nt, ri)
			ri.addInstr("JMP", label2, "LABEL")
			ri.addLabel(label1)
			self.fBody.translate(nt, ri)
			ri.addLabel(label2)
		else:
			ri.addfInstr("LD", temp1, "TEMP")
                        ri.addToAR(temp1, "TEMP")
			ri.addfInstr("JMN", label1, "LABEL")
                        ri.addfInstr("JNZ", label1, "LABEL")
                        self.tBody.translate(nt, ri)
                        ri.addfInstr("JMP", label2, "LABEL")
                        ri.addLabel(label1)
                        self.fBody.translate(nt, ri)
                        ri.addLabel(label2)


	def display( self, nt, ft, depth=0 ) :
		print "%sIF" % (tabstop*depth)
		self.cond.display( nt, ft, depth+1 )
		print "%sTHEN" % (tabstop*depth)
		self.tBody.display( nt, ft, depth+1 )
		print "%sELSE" % (tabstop*depth)
		self.fBody.display( nt, ft, depth+1 )


class WhileStmt( Stmt ) :

	def __init__( self, cond, body ) :
		self.cond = cond
		self.body = body

	def eval( self, nt, ft ) :
		while self.cond.eval( nt, ft ) > 0 :
			self.body.eval( nt, ft )

	def translate( self, nt, ri):
		label1 = ri.getNextLabel()
		label2 = ri.getNextLabel()
		
		if(ri.currentFunction == "main"):
			ri.addLabel(label1)
			temp1 = self.cond.translate(nt,ri)
			ri.addInstr("LD", temp1, "TEMP")
			ri.addInstr("JMN", label2, "LABEL")
			ri.addInstr("JMZ", label2, "LABEL")
			self.body.translate(nt, ri)
			ri.addInstr("JMP", label1, "LABEL")
			ri.addLabel(label2) 
		else:
			ri.addLabel(label1)
                        temp1 = self.cond.translate(nt,ri)
                        ri.addfInstr("LD", temp1, "TEMP")
                        ri.addToAR(temp1, "TEMP")
			ri.addfInstr("JMN", label2, "LABEL")
                        ri.addfInstr("JMZ", label2, "LABEL")
                        self.body.translate(nt, ri)
                        ri.addfInstr("JMP", label1, "LABEL")
                        ri.addLabel(label2)

	def display( self, nt, ft, depth=0 ) :
		print "%sWHILE" % (tabstop*depth)
		self.cond.display( nt, ft, depth+1 )
		print "%sDO" % (tabstop*depth)
		self.body.display( nt, ft, depth+1 )

#-------------------------------------------------------

class StmtList :
	'''builds/stores a list of Stmts'''

	def __init__( self ) :
		self.sl = []
	
	def insert( self, stmt ) :
		self.sl.insert( 0, stmt )
	
	def eval( self, nt, ft ) :
		for s in self.sl :
			s.eval( nt, ft )
	
	def translate(self, nt, ri):
		for s in self.sl :
			s.translate(nt, ri)	
		#TODO: IS THIS THE BEST PLACE TO DO THIS?
		for sIndex in range(len(ri.instrList)):
			if ri.instrList[sIndex].func == 'ST':
				ri.instrList[sIndex].func = 'STA'
			if ri.instrList[sIndex].func == 'LD':
				ri.instrList[sIndex].func = 'LDA'

	def optimize(self,ri):
		toRemove = []
		for sIndex in range(len(ri.instrList)-1):
			#IF sIndex is STORE N, and sIndex is LOAD N, add the load to the Remove list
			if ri.instrList[sIndex].func.find('ST') != -1 and ri.instrList[sIndex+1].func.find('LD') != -1 and ri.instrList[sIndex].operand==ri.instrList[sIndex+1].operand:
				toRemove.append(sIndex+1)
		while len(toRemove) > 0:
			ri.instrList.pop(toRemove.pop())#Removing in reverse order leaves earlier indexes unchanged

	def display( self, nt, ft, depth=0 ) :
		print "%sSTMT LIST" % (tabstop*depth)
		for s in self.sl :
			s.display( nt, ft, depth+1 )


class Proc :

	def __init__(self, paramList, body):
		self.parList = paramList
		self.body = body

	def apply(self, nt, ft, args):
		newContext = {}

		if len(args) is not len(self.parList):
			print "Param count does not match:"
			sys.exit(1)
		for i in range (len(args)):
			newContext[ self.parList[i] ] = args[i].eval(nt,ft)

		self.body.eval(newContext,ft)
		if newContext.has_key(returnSymbol):
			return newContext[returnSymbol]
		else:
			print "Error: no return value"
			sys.exit(2)

	def translate(self, nt, ri):
		for p in self.parList:
#			print "Param : "+ p
			ri.fParamTable.append(TableEntry(p,0))
#		temp1 = "FT1"
#		local1 = "FL1"
#		ri.addToAR(temp1, "TEMP")
#		ri.addToAR(local1, "LOCAL")
		self.body.translate(nt,ri)
#		ri.dumpAR()
	def display(self, nt, ft, depth=0):
		print "%sPROC %s :" % (tabstop*depth, str(self.parList))
		self.body.display(nt,ft,depth+1)

class Program :
	
	def __init__( self, stmtList ) :
		self.stmtList = stmtList
		self.nameTable = {}
		self.funcTable = {}
		self.RAMinfo = RAMInfo()
	
	def eval( self ) :
		self.stmtList.eval( self.nameTable, self.funcTable )
	
	def translate(self) :
		self.stmtList.translate(self.nameTable, self.RAMinfo)
		self.RAMinfo.addInstr("HLT", "", "UNDEF")	

	def addFuncInstr(self):
		one = -1
		for oneIndex in range(len(self.RAMinfo.constValueTable)):
			if self.RAMinfo.constValueTable[oneIndex]==1:
				one = oneIndex
				break
		if one == -1:
			one = self.RAMinfo.getNextConst(1)
		for i in range(0, len(self.RAMinfo.funcTable)):
			print "adding " + self.RAMinfo.funcTable[i].name
			for k in range(0, len(self.RAMinfo.funcTable[i].ilist)):
				#DO THE TRANSLATE FOR LOAD
				if self.RAMinfo.funcTable[i].ilist[k].func == "LD":
					instr = Instruction("LDA","FP", self.RAMinfo.lineCount,"FP")
					self.RAMinfo.instrList.append(instr)
					self.RAMinfo.lineCount = self.RAMinfo.lineCount + 1
					pos = 0
					if self.RAMinfo.funcTable[i].ilist[k].operand[0] == "P":
						pos = int(self.RAMinfo.funcTable[i].ilist[k].operand[1:])
					if self.RAMinfo.funcTable[i].ilist[k].operand[0:1] == "FL":
						pos = self.RAMinfo.funcTable[i].paramCount + int(self.RAMinfo.funcTable[i].ilist[k].operand[2:])
					if self.RAMinfo.funcTable[i].ilist[k].operand[0:1] == "FT":
						pos = self.RAMinfo.funcTable[i].paramCount + self.RAMinfo.funcTable[i].localCount + int(self.RAMinfo.funcTable[i].ilist[k].operand[2:])
					for oneAddition in range(pos):
						instr = Instruction("ADD",one, self.RAMinfo.lineCount,"CONST")
						self.RAMinfo.instrList.append(instr)
						self.RAMinfo.lineCount = self.RAMinfo.lineCount + 1
					instr = Instruction("STA","FPB", self.RAMinfo.lineCount,"FPB")
					self.RAMinfo.instrList.append(instr)
					self.RAMinfo.lineCount = self.RAMinfo.lineCount + 1
					instr = Instruction("LDI","FPB", self.RAMinfo.lineCount,"FPB")
					self.RAMinfo.instrList.append(instr)
					self.RAMinfo.lineCount = self.RAMinfo.lineCount + 1
					continue
				#DO THE TRANSLATE FOR STORE
				if self.RAMinfo.funcTable[i].ilist[k].func == "ST":
					instr = Instruction("STA","SCRATCH", self.RAMinfo.lineCount,"SCRATCH")
					self.RAMinfo.instrList.append(instr)
					self.RAMinfo.lineCount = self.RAMinfo.lineCount + 1
					instr = Instruction("LDA","FP", self.RAMinfo.lineCount,"FP")
					self.RAMinfo.instrList.append(instr)
					self.RAMinfo.lineCount = self.RAMinfo.lineCount + 1
					pos = 0
					if self.RAMinfo.funcTable[i].ilist[k].operand[0] == "P":
						pos = int(self.RAMinfo.funcTable[i].ilist[k].operand[1:])
					if self.RAMinfo.funcTable[i].ilist[k].operand[0:1] == "FL":
						pos = self.RAMinfo.funcTable[i].paramCount + int(self.RAMinfo.funcTable[i].ilist[k].operand[2:])
					if self.RAMinfo.funcTable[i].ilist[k].operand[0:1] == "FT":
						pos = self.RAMinfo.funcTable[i].paramCount + self.RAMinfo.funcTable[i].localCount + int(self.RAMinfo.funcTable[i].ilist[k].operand[2:])
					for oneAddition in range(pos):
						instr = Instruction("ADD",one, self.RAMinfo.lineCount,"CONST")
						self.RAMinfo.instrList.append(instr)
						self.RAMinfo.lineCount = self.RAMinfo.lineCount + 1
					instr = Instruction("STA","FPB", self.RAMinfo.lineCount,"FPB")
					self.RAMinfo.instrList.append(instr)
					self.RAMinfo.lineCount = self.RAMinfo.lineCount + 1
					instr = Instruction("LDA","SCRATCH", self.RAMinfo.lineCount,"SCRATCH")
					self.RAMinfo.instrList.append(instr)
					self.RAMinfo.lineCount = self.RAMinfo.lineCount + 1
					instr = Instruction("STI","FPB", self.RAMinfo.lineCount,"FPB")
					self.RAMinfo.instrList.append(instr)
					self.RAMinfo.lineCount = self.RAMinfo.lineCount + 1
					continue
				instr = Instruction(self.RAMinfo.funcTable[i].ilist[k].func, self.RAMinfo.funcTable[i].ilist[k].operand, self.RAMinfo.lineCount, self.RAMinfo.funcTable[i].ilist[k].varType)
				self.RAMinfo.instrList.append(instr)
				if(self.RAMinfo.funcTable[i].ilist[k].varType != "LABEL"):
					self.RAMinfo.lineCount = self.RAMinfo.lineCount + 1
			
	def optimize(self):
		self.stmtList.optimize(self.RAMinfo)#Don't need nametable?

	def dump( self ) :
		print "Dump of Symbol Table"
		print "Name Table"
		for k in self.nameTable :
			print "  %s -> %s " % ( str(k), str(self.nameTable[k]) )
		print "Function Table"
		for k in self.funcTable :
			print "  %s" % str(k)

	def display( self, depth=0 ) :
		print "%sPROGRAM :" % (tabstop*depth)
		self.stmtList.display( self.nameTable, self.funcTable )

